

// LCR 096.交错字符串
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        // 使用动态规划来实现
        // dp[i][j]表示s1的[1,i]和s2的[1,j]能否拼成s3的[1,i+j]
        int n = s1.size() , m = s2.size();
        if(n + m != s3.size()) return false;
        s1 = " " + s1 , s2 = " " + s2;
        s3 = " " + s3;
        vector<vector<bool>> dp(n + 1 , vector<bool>(m + 1));
        dp[0][0] = true;
        for(int i = 1 ; i <= n ; i++ )      // 第一列
            if(s1[i] == s3[i]) dp[i][0] = true;
            else break;
        
        for(int i = 1 ; i <= m ; i++)       // 第一行
            if(s2[i] == s3[i]) dp[0][i] = true;
            else break;

        // 开始进行DP
        for(int i = 1 ; i <= n ; i++)
        {
            for(int j = 1; j <= m ; j++)
                dp[i][j] = (dp[i - 1][j] && s1[i] == s3[i + j])|| (dp[i][j - 1] && s2[j] == s3[i + j]);
        }
        return dp[n][m];
    } 
};